//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/?favorite=xb9nqhhg&orderBy=most_votes&languageTags=c

//剑指 Offer 57. 和为s的两个数字

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    *returnSize = 2;
    int* ret = (int*)malloc(sizeof(int) * 2);
    int left = 0;
    int right = numsSize - 1;
    int mid = (left + right) / 2;
    while (nums[right]>target)//判断区间
    {
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            right--;
        }
        mid = (left + right) / 2;
    }  
    while(left<right)
    {
            if (nums[left] + nums[right] < target)
                left++;
            else if (nums[left] + nums[right] > target)
                right--;
           else
            {
                ret[0] = nums[left];
                ret[1] = nums[right];
                return ret;
            }
    }
    
    *returnSize=0;
    return NULL;
}